
let MapInfo = {
    createMap: function (mapLH) { 
        let map = [];
        let mapSize = mapLH * mapLH;
        for (let i = 0; i < mapSize; i++){
            map.push(1);
            let row = Math.floor(i / mapLH);
            let line = i % mapLH;
            if (row < 2 && line == 1) {
                map[i] = 100;
            }
            if (row >= mapLH - 2 && line == mapLH - 2){
                map[i] = 100;
            }
        }
        return map;
    },

    printMap: function (map) { 
        let mapLH = Math.sqrt(map.length);
        for (let i = 0; i < mapLH; i++){
            let str = "";
            for (let j = 0; j < mapLH; j++){
                if (map[i * mapLH + j] == 100) {
                    str += "* ";
                } else if(map[i * mapLH + j] == 999) {
                    str += "1 ";
                } else {
                    str += "+ ";
                }
            }
            console.log(str);
        }
    }, 
};

class MapNode { 
    constructor(idx, f) {
        this.idx = idx;
        this.f = f;
        this.parent = null;
    }

    getRowLine(mapLH) { 
        let row = Math.floor(this.idx / mapLH);
        let line = this.idx % mapLH;
        return [row, line];
    }
};
class MapAStar { 
    constructor(map) { 
        this.map = map;
        this.mapLH = Math.sqrt(this.map.length);
        this.open = [];
        this.close = [];
    }
    
    isInOC(idx) {
        for (let i = 0; i < this.open.length; i++){
            if (this.open[i].idx == idx) {
                return true;
            }
        }
        for (let i = 0; i < this.close.length; i++){
            if (this.close[i].idx == idx) {
                return true;
            }
        }
        return false;
    }

    plusToOpen(idx, p, t, e) {
        let row1 = Math.floor(idx / this.mapLH);
        let line1 = idx % this.mapLH;
        let row2 = Math.floor(e / this.mapLH);
        let line2 = e % this.mapLH;
        let h = Math.abs(row1 - row2) + Math.abs(line1 - line2);
        let g = p.f + t;
        let f = g + h;
        let mapNode = new MapNode(idx, f);
        mapNode.parent = p;
        for (let i = 0; i < this.open.length; i++){
            if (mapNode.f < this.open[i].f) {
                this.open.splice(i, 0, mapNode);
                return;
            }
        }
        this.open.push(mapNode);
    }
};

let mapLH = 6;
let map = MapInfo.createMap(mapLH);
MapInfo.printMap(map);
console.log("-------------------------");

let start = 0;
let end = map.length - 1;
let mapAStar = new MapAStar(map);
let p = new MapNode(start, 0);
mapAStar.open.push(p);

while (true) {
    if (mapAStar.open.length == 0) {
        p = null;
        break;
    }
    p = mapAStar.open[0];
    if (p.idx == end) {
        break;
    }
    mapAStar.open.splice(0, 1);
    mapAStar.close.push(p);
    let [row, line] = p.getRowLine(mapLH);
    // top
    if (row - 1 >= 0) {
        let idx = (row - 1) * mapLH + line;
        if (map[idx] != 100 && !mapAStar.isInOC(idx)) {
            let t = map[idx] * 1;
            mapAStar.plusToOpen(idx, p, t, end);
        }
    }
    // bot
    if (row + 1 < mapLH) {
        let idx = (row + 1) * mapLH + line;
        if (map[idx] != 100 && !mapAStar.isInOC(idx)) {
            let t = map[idx] * 1;
            mapAStar.plusToOpen(idx, p, t, end);
        }
    }
    // left
    if (line - 1 >= 0) {
        let idx = row * mapLH + line - 1;
        if (map[idx] != 100 && !mapAStar.isInOC(idx)) {
            let t = map[idx] * 1;
            mapAStar.plusToOpen(idx, p, t, end);
        }
    }
    // right
    if (line + 1 < mapLH) {
        let idx = row * mapLH + line + 1;
        if (map[idx] != 100 && !mapAStar.isInOC(idx)) {
            let t = map[idx] * 1;
            mapAStar.plusToOpen(idx, p, t, end);
        }
    }
}
if (p) {
    while (p) {
        map[p.idx] = 999;
        p = p.parent;
    }
    MapInfo.printMap(map);
}
else {
    console.log("no way");
}